class Disjoint_sets():
    def __init__(self):
        self.p={} #node:parent
        self.rank={} #node:rank
    def makeset(self,x):
        self.p[x]=x
        self.rank[x]=0
    def union(self,x,y):
        self.link(self.find_set(x), self.find_set(y))
    def link(self,x,y): #x and y are roots: p[x]==x and p[y]==y
        if self.rank[x]>self.rank[y]:
            self.p[y]=x
        else:
            self.p[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1
    def find_set(self,x):
        path=[]
        curr=x
        while curr!=self.p[curr]:
            path.append(curr)
            curr=self.p[curr]
        for i in path:
            self.p[i]=curr
        return curr
 
if __name__=='__main__':
    a=Disjoint_sets()
    a.makeset(0)
    a.makeset(1)
    a.makeset(2)
    a.makeset(3)
    a.makeset(4)
    print 'node:parent ', a.p
    print 'node:rank ', a.rank
    a.union(0,2)
    a.union(3,4)
    a.union(0,3)
    a.union(1,2)
    print 'node:parent ', a.p
    print 'node:rank ', a.rank
